import java.util.TreeMap;

/**
 * 732. 我的日程安排表 III
 * https://leetcode-cn.com/problems/my-calendar-iii/
 */
public class Solutions_732 {
    public static void main(String[] args) {
        MyCalendarThree obj = new MyCalendarThree();
        int res1 = obj.book(10, 20);  // output: 1
        System.out.println(res1);
        int res2 = obj.book(50, 60);  // output: 1
        System.out.println(res2);
        int res3 = obj.book(10, 40);  // output: 2
        System.out.println(res3);
        int res4 = obj.book(5, 15);  // output: 3
        System.out.println(res4);
        int res5 = obj.book(5, 10);  // output: 3
        System.out.println(res5);
        int res6 = obj.book(25, 55);  // output: 3
        System.out.println(res6);
//        解释:
//        前两个日程安排可以预订并且不相交，所以最大的K次预订是1。
//        第三个日程安排[10,40]与第一个日程安排相交，最高的K次预订为2。
//        其余的日程安排的最高K次预订仅为3。
//        请注意，最后一次日程安排可能会导致局部最高K次预订为2，但答案仍然是3，原因是从开始到最后，时间[10,20]，[10,40]和[5,15]仍然会导致3次预订。
    }
}

/**
 * 解法二：线段树（14ms）
 */
class MyCalendarThree {
    int res = 0;
    SegmentTreeNode root;

    public MyCalendarThree() {
        root = new SegmentTreeNode(0, 0);
    }

    public int book(int start, int end) {
        // 计算得到本次查询的结果
        int max = book(root, start, end, 0, false);
        // 最终返回的是最大值 res
        res = Math.max(res, max);
        return res;
    }

    /**
     * 查找过程中，完成构造线段树
     */
    public int book(SegmentTreeNode node, int start, int end, int depth, boolean inner) {
        if (inner) {
            if (node.inner == null) {
                node.inner = new SegmentTreeNode(start, end);
                return depth + 1;
            }
            node = node.inner;
        }
        while (true) {
            // 三种情况：
            // 1. node.end <= start，[start, end) 区间在线段的右边
            // 例：线段：[10, 30) 与区间：[40, 50)

            // 2. node.start >= end，[start, end) 区间在线段的的左边
            // 例：线段：[10, 30) 与区间：[5, 10)

            // 3. 相交（有重叠部分）

            if (node.end <= start) {
                if (node.right == null) {
                    // 在线段右边，构造一个线段对象
                    node.right = new SegmentTreeNode(start, end);
                    return depth + 1;
                } else {
                    // 继续获取
                    node = node.right;
                }
            } else if (node.start >= end) {
                if (node.left == null) {
                    // 在线段左边，构造一个线段对象
                    node.left = new SegmentTreeNode(start, end);
                    return depth + 1;
                } else {
                    // 继续获取
                    node = node.left;
                }
            } else {
                // 相交时，存在四种情况：
                // 1. start < node.start && end <= node.end
                // 例：线段：[10, 30)，区间：[5, 15)，两部分：不重叠区间：[5, 10)，重叠区间：[10, 15)

                // 2. start < node.start && end > node.end
                // 例：线段：[10, 30)，区间：[5, 35)，三部分：不重叠区间：[5, 10)，重叠区间：[10, 30]，不重叠区间：[31, 35)

                // 3. start >= node.start && end <= node.end
                // 例：线段：[10, 30)，区间：[13, 30)，一部分：重叠区间：[13, 30)

                // 4. start >= node.start && end > node.end
                // 例：线段：[10, 30)，区间：[13, 35)，两部分：重叠区间：[13, 30)，不重叠区间：[30, 35)

                if (start < node.start) {
                    if (end <= node.end) {
                        int ans1 = book(node, start, node.start, depth, false);
                        int ans2 = book(node, node.start, end, depth + 1, true);
                        return Math.max(ans1, ans2);
                    } else if (end > node.end) {
                        int ans1 = book(node, start, node.start, depth, false);
                        int ans2 = book(node, node.start, node.end, depth + 1, true);
                        int ans3 = book(node, node.end, end, depth, false);
                        return Math.max(Math.max(ans1, ans2), ans3);
                    }
                } else {
                    if (end <= node.end) {
                        int ans = book(node, start, end, depth + 1, true);
                        return ans;
                    } else if (end > node.end) {
                        int ans1 = book(node, start, node.end, depth + 1, true);
                        int ans2 = book(node, node.end, end, depth, false);
                        return Math.max(ans1, ans2);
                    }
                }
            }
        }
    }
}

class SegmentTreeNode {
    // 根节点的区间为：[start, end)
    int start, end;
    SegmentTreeNode left, right, inner;

    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

/**
 * 解法一：TreeMap 实现（差分数组形式）（133ms）
 */
class MyCalendarThree2 {
    // start 和 end 的取值范围为 [0, 10^9]，因数值太大，所以无法用数组来表示
    // {10, 3}，表示日程 10 时，预定次数有 3 次
    TreeMap<Integer, Integer> treeMap = null;

    public MyCalendarThree2() {
        treeMap = new TreeMap<>();
    }

    public int book(int start, int end) {
        // start 时上车，end 时下车，那么在 [start, end) 区间中，共有 1 人存在
        treeMap.put(start, treeMap.getOrDefault(start, 0) + 1);
        treeMap.put(end, treeMap.getOrDefault(end, 0) - 1);
        int res = 0;

        int temp = 0;
        // 差分数组形式（计算得到日程上相交的最大次数）
        for (int count : treeMap.values()) {
            temp += count;
            if (temp > res) {
                // 更新最大相交次数
                res = temp;
            }
        }
        return res;
    }
}
